package 判断一个树是否是另一棵树的子树;

import javax.swing.tree.TreeNode;

public class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null){  // 缺少会空指针异常
            return false;
        }

        // 到这说明 root 和 subRoot 都不空
        // 判断是否相同
        if (isSameTree(root,subRoot)){
            return true;
        }

        // 在左子树找
        if (isSubtree(root.left,subRoot)){
            return true;
        }

        // 在右子树找
        if (isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }



    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if ((q == null && p != null) || (q != null && p == null)) {
            return false;
        }
        if (q != null && p != null) {
            if (q.val != p.val) {        // 这里不能用相等，因为根相等，左右子树不一定相等
                return false;
            }
        }
        boolean retleft = isSameTree(p.left, q.left);
        boolean retright = isSameTree(p.right, q.right);
        return retleft && retright;

    }
}
